package leetcode.editor.day;

import java.util.*;

// 658. 找到 K 个最接近的元素
// https://leetcode.cn/problems/find-k-closest-elements/
class FindKClosestElements {
    public static void main(String[] args) {
        Solution solution = new FindKClosestElements().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 排序
    /*public List<Integer> findClosestElements(int[] arr, int k, int x) {
        LinkedList<Integer> res = new LinkedList<>();

        for (int num : arr) {
            res.add(num);
        }

        Collections.sort(res, (o1, o2) -> {
            if (Math.abs(o1 - x) != Math.abs(o2 - x)) {
                return Math.abs(o1 - x) - Math.abs(o2 - x);
            } else {
                return o1 - o2;
            }
        });

        List<Integer> list = res.subList(0, k);
        Collections.sort(list);

        return list;
    }*/

        // 二分 + 双指针
        // https://leetcode.cn/problems/find-k-closest-elements/solution/zhao-dao-k-ge-zui-jie-jin-de-yuan-su-by-ekwtd/
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            int r = binarySearch(arr, x);
            int l = r - 1;
            while (k > 0) {
                if (l < 0) {
                    r++;
                } else if (r > arr.length - 1) {
                    l--;
                } else if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) {
                    l--;
                } else {
                    r++;
                }
                k--;
            }

            LinkedList<Integer> res = new LinkedList<>();
            for (int i = l + 1; i < r; i++) {
                res.add(arr[i]);
            }

            return res;
        }

        public int binarySearch(int[] arr, int x) {
            int l = 0, r = arr.length;
            while (l < r) {
                int m = l + (r - l) / 2;
                if (arr[m] >= x) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }

            return l;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
